package com.tgy.algorithm._经典题目01;

import com.tgy.algorithm._经典题目01._review._查找第k小的值;

import java.util.Arrays;

/**
 * 长度为N的数组arr，一定可以组成N^2个数值对，
 * 例如arr = [3,1,2]，数值对有(3,3) (3,1) (3,2) (1,3) (1,1)(1,2) (2,3) (2,1)(2,2)
 * 也就是任意两个数都有数值对，而且自己和自己也算数值对数值对
 * 怎么排序?规定，第一维数据从小到大，第一维数据一样的，第二维数组也从小到大。
 * 所以上面的数值对排序的结果为:(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3)
 * 给定一个数组ar，和整数k，返回第k小的数值对
 */
public class _014_二位数的第k小的值 {

    // 第k小 1 2 3
    public static int[] findK(int[] nums, int k) {

        if (nums == null || nums.length == 0) {
            return null;
        }

        int len = nums.length;
        if (len *len < k) {
            return null;
        }

        int[] ret = new int[2];

        // k = 3 0 k = 4 => 1

        int index = (int)((k  - 1) / len);

        // 查找第index小的数，index从0开始
        int kValue = _查找第k小的值.findKValue(nums, index + 1);

        ret[0] = kValue;
        int ltCount = 0;
        int eqCount = 0;

        for (int i = 0; i < len; i++) {
            if (nums[i] < kValue) {
                ltCount++;
            }else if(nums[i] == kValue) {
                eqCount++;
            }
        }

        // 11 -
        int rest = k - ltCount * len;
        ret[1] = _查找第k小的值.findKValue(nums,((rest - 1) / eqCount) + 1);
        return ret;
    }

    public static void main(String[] args) {
        int[] nums = {3,3,1,2};
        int[] k = findK(nums, 11);
        System.out.println(Arrays.toString(k));
    }
}
